/**
 * Copyright 2012 Roman Seleznov
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License. 
 */

package com.romanapps.algorithms.sort;

import java.util.List;

public class MergeSort<T extends Comparable<? super T>> implements Sort<T>{

	@Override
	public List<T> sort(List<T> sortList) {
		for ( int step = 1; step<sortList.size(); step=step*2 ){
			merge( step, sortList );
		}
		return sortList;		
	}
	
	private void merge( int step, List<T> sortList ){
		
		for( int i = 0; i<sortList.size(); i=i+step*2 ){			
			
			int shift = 0;  //number of inserted items
			int cursor = i; //position of last inserted item
			
			for( int j = i+step; j<i+step*2 && j<sortList.size(); j++ ){
				T item2 = sortList.get(j);//item from second list
				
				boolean noPlaceFound = true;
				
				for( int k = cursor; k<i+step+shift; k++ ){
					T item1 = sortList.get( k );//item from first list
					
					if( item2.compareTo(item1) < 1 ){
						sortList.remove( j );
						sortList.add( k, item2 );
						shift++;
						cursor = k;
						noPlaceFound = false;
						break;
					}				
				}//for
				
				/* 
				 * Will break here because list is sorted, and
				 * all items coming after are even higher than current.
				 */
				if( noPlaceFound ){
					break;
				}
				
			}//for
			
		}//for		
		
	}
	
}
